package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 1/29/21 11:46 AM
 */
public class _02_打印二叉树的边界节点 {

    /**
     * 1.头节点为边界点
     * 2.叶节点为边界点
     * 3.同一层点最左最右的节点为边界点
     * @param root
     */
    public static void printBinaryTreeEdgeNode(TreeNode root) {

        if (root == null) {

            return;
        }

        Stack<TreeNode> stack = new Stack<>();

        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        int levelNum = 1,levelCount = 0;


        while (!queue.isEmpty()) {

            TreeNode node = queue.poll();

            if (node.left != null) {

                queue.offer(node.left);
            }

            if (node.right != null) {

                queue.offer(node.right);
            }

            if (levelCount == 0) {

                System.out.println(node.val);
            }else if (levelCount == levelNum - 1) {

                stack.push(node);
            }else if (node.left == null && node.right == null){

                System.out.println(node.val);
            }

            levelCount++;

            if (levelCount == levelNum) {

                levelCount = 0;
                levelNum = queue.size();
            }
        }

        while (!stack.isEmpty()) {

            System.out.println(stack.pop().val);
        }

    }


    public static void printBinaryTreeEdgeAndLeafNode(TreeNode root) {

        if (root == null) {

            return;
        }

        System.out.println(root.val);

        if (root.left != null && root.right != null) {

            printLeftEdgeAndLeafNode(root.left,true);
            printRightEdgeAndLeafNode(root.right,true);
        }else {

            printBinaryTreeEdgeAndLeafNode(root.left != null ? root.left:root.right);
        }

    }

    /**
     * 前序遍历
     * @param node
     * @param isPrint
     */
    public static void printLeftEdgeAndLeafNode(TreeNode node, boolean isPrint) {

        if (node == null) {

            return;
        }

        if (isPrint || (node.left == null && node.right == null)) {

            System.out.println(node.val);
        }

        printLeftEdgeAndLeafNode(node.left,isPrint);
        printLeftEdgeAndLeafNode(node.right,isPrint && node.left == null);

    }

    /**
     * 后序遍历
     * @param node
     * @param isPrint
     */
    public static void printRightEdgeAndLeafNode(TreeNode node,boolean isPrint) {

        if (node == null) {

            return;
        }

        printRightEdgeAndLeafNode(node.left,isPrint && node.right == null);
        printRightEdgeAndLeafNode(node.right,isPrint);


        if (isPrint || (node.left == null && node.right == null)) {

            System.out.println(node.val);
        }
    }


    public static void main(String[] args) {

        /**
         *
         *          3
         *        /  \
         *       1    5
         *       \   /
         *       2  4
         *      / \
         *    -10 -20
         *          \
         *          -30
         *          /
         *         -40
         */
        TreeNode root = new  TreeNode(3);

        root.left = new TreeNode(1);
        root.right = new TreeNode(5);
//        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(-10);
        root.left.right.right = new TreeNode(-20);
        root.left.right.right.right = new TreeNode(-30);
        root.left.right.right.right.left = new TreeNode(-40);

        root.right.left = new TreeNode(4);

        printBinaryTreeEdgeAndLeafNode(root);
    }
}
